//
//  Graph.swift
//  DataStructuresAlgorithms
//
//  Created by xiangzuhua on 2021/3/18.
//

import UIKit

class Graph: NSObject {
    private var vetex: Int
    private var adj: [LinkList<Int>]
    init(_ vetex: Int) {
        self.vetex = vetex
        self.adj = [LinkList<Int>](repeating: LinkList(), count: vetex)
    }
    
    public func addEdige(bothway a: Int, b:Int ){
        adj[a].append(b)
        adj[b].append(a)
    }
    
    public func addEdige(from a: Int, to b: Int){
        adj[a].append(b)
    }
    
    // 广度优先搜索
    public func bfs(_ start: Int, _ end: Int){
        if start == end {
            return
        }
        
        // 记录节点是否已访问
        var visited = [Bool](repeating: false, count: vetex)
        visited[start] = true
        
        // 队列，存储将要访问的节点，以先进先出的方式取
        var queue = LinkList<Int>()
        queue.append(start)
        
        // 存储搜索路径，反向存储，比如，我们通过顶点2的邻接表访问到顶点3，那prev[3]就等于2
        var prev = [Int](repeating: -1, count: vetex)
        
        while queue.size() != 0 {
            let front = queue.pop()!
            for i in 0..<(adj[front].size()) {
                let temp = adj[front].get(index: i)!
                if !visited[temp] {
                    prev[temp] = front
                    if temp == end {
                        // 到达终点
                        printPrev(prev, start: start, end: end)
                        return
                    }
                    visited[temp] = true
                    queue.append(temp)
                }
            }
        }
        
    }
    
    
    // 深度优先搜索
    var found:Bool = false
    public func dfs(_ start: Int, end: Int){
        found = false
        var visited = [Bool](repeating: false, count: vetex)
        var prev = [Int](repeating: -1, count: vetex)
        recurDfs(start, end: end, visited: &visited, prev: &prev)
        printPrev(prev, start: start, end: end)
        
    }
    
    func recurDfs(_ start: Int, end: Int, visited:inout [Bool], prev:inout [Int]){
        if found {
            return
        }
        visited[start] = true
        if start == end {
            found = true
            return
        }
        
        for i in 0..<adj[start].size() {
            let temp = adj[start].get(index: i)!
            if !visited[temp] {
                prev[temp] = start
                recurDfs(temp, end: end, visited: &visited, prev: &prev)
            }
        }
        
    }
    
    func printPrev(_ prev: [Int], start: Int, end: Int) {
        if prev[end] != -1 && end != start {
            printPrev(prev, start: start, end: prev[end])
        }
        print("\(end) ")
    }
    
    // MARK:-拓扑排序
    //Kahn算法
    public func topoSortByKahn(){
        // 统计每个顶点的入度
        var inDegree = [Int](repeating: 0, count: vetex)
        for i in 0..<vetex {
            let length = adj[i].size()
            for j in 0..<length {
                let temp = adj[i].get(index: j)!
                inDegree[temp] += 1
            }
        }
        
        // 取出入度为0的顶点，放入队列
        var queue = LinkList<Int>()
        for i in 0..<vetex {
            if inDegree[i] == 0 {
                queue.push(i)
            }
        }
        
        // 入度为0的顶点出队列，然后将顶点对应的出度清理掉，剩下的顶点中入度变为0的继续加入队列
        while !queue.isEmpty() {
            let temp = queue.removeLast()!
            print(" -> \(temp)")
            for i in 0..<adj[temp].size() {
                let k = adj[temp].get(index: i)!
                inDegree[k] -= 1
                if inDegree[k] == 0 {
                    queue.push(k)
                }
            }
        }
    }
    
    // DFS算法
    public func topoSortDFS(){
        // 创建逆邻接表
        var inverseAdj = [LinkList<Int>](repeating: LinkList<Int>(), count: vetex)
        // 根据邻接表生成逆邻接表
        for i in 0..<vetex {
            for j in 0..<adj[i].size(){
                let k = adj[i].get(index: j)!
                inverseAdj[k].append(i)
            }
        }
        
        // 深度优先遍历
        var visited = [Bool](repeating: false, count: vetex)
        for i in 0..<vetex {
            if !visited[i] {
                visited[i] = true
                topoDfs(i, inverseAdj: inverseAdj, visited: &visited)
            }
        }
        
        
    }
    
    private func topoDfs(_ vertex: Int, inverseAdj: [LinkList<Int>], visited: inout [Bool]){
        let linklist = inverseAdj[vertex]
        for i in 0..<linklist.size() {
            let k = linklist.get(index: i)!
            if visited[k] {
                continue
            }
            visited[k] = true
            topoDfs(k, inverseAdj: inverseAdj, visited: &visited)
        }
        print("->\(vertex)")
    }
    
}

